#include <bits/stdc++.h>

using namespace std;

// 给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：
// |x - y| <= min(x, y)
// 你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数
// 对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。
// 返回数组 nums 所有可能的强数对中的 最大 异或值。
// 注意，你可以选择同一个整数两次来形成一个强数对。
// 测试链接：https://leetcode.cn/problems/maximum-strong-pair-xor-ii/

class Solution 
{
private:
    // 准备这么多静态空间就够了，实验出来的
	// 如果测试数据升级了规模，就改大这个值
    static const int MAXN = 280001;
    int tree[MAXN][2];
    int pass[MAXN];
    int cnt = 1; // 节点编号x
    // 数字只需要从哪一位开始考虑
    int high = 19;

    void insert(int x)
    {
        int cur = 1;
        ++pass[cur];
        for(int i = high, path; i >= 0; --i)
        {
            path = (x >> i) & 1;
            if(tree[cur][path] == 0)
            {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            ++pass[cur];
        }
    }

    void remove(int x)
    {
        int cur = 1;
        --pass[cur]; 
        for(int i = high, path; i >= 0; --i)
        {
            path = (x >> i) & 1;
            if(--pass[tree[cur][path]] == 0)
            {
                // 将 tree[cur][path] 设置为 0 就
                // 能够表示后续的节点都被释放了，尽
                // 后面来了一个相同的数字也不会影响
                // maxXor 的结果，因为 insert 数据
                // 会重新分配一个编号 cnt，这样就无
                // 法使用到原来的数据了
                tree[cur][path] = 0;
                return;
            }
            cur = tree[cur][path];
        }
    }

    int maxXor(int x)
    {
        // 最终异或的结果(尽量大)
        int ans = 0;
        // 前缀树目前来到的节点编号
		int cur = 1;
        for(int i = high, want, status; i >= 0; --i)
        {
			// status : x 第 i 位的状态
            status = (x >> i) & 1;
            // want : x 第 i 位希望遇到的状态
            want = status ^ 1;
            if(tree[cur][want] == 0) // 询问前缀树，能不能达成
            {
                // 不能达成
                want ^= 1;
            }
            // want 变成真的往下走的路
            ans |= (status ^ want) << i;
            cur = tree[cur][want];
        }
        return ans;
    }

public:
    int maximumStrongPairXor(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        // |x - y| <= min(x, y)
        // x <= y ==> y - x <= x ==> y <= 2 * x
        int left = 0, ans = 0;
        for(int y : nums)
        {
            insert(y);
            // 移除不满足的条件的 nums[left]
            while(nums[left] * 2 < y) remove(nums[left++]);
            ans = max(ans, maxXor(y));
        }
        return ans;
    }
};